package com.ljx.DijkStra;

import java.util.*;

/**
 * @author 李加喜
 * @Package com.ljx.DijkStra
 * @date 2021-11-10 23:01
 */

/**
 *  最小体力消耗
 */
public class MinTiLi {
    public static void main(String[] args) {

    }
    class State {
        // 矩阵中的一个位置
        int x, y;
        // 从起点 (0, 0) 到当前位置的最小体力消耗（距离）
        int effortFromStart;

        State(int x, int y, int effortFromStart) {
            this.x = x;
            this.y = y;
            this.effortFromStart = effortFromStart;
        }
    }
    List<int[]> adj(int[][] matrix, int x, int y) {
        int m = matrix.length, n = matrix[0].length;
        // 存储相邻节点
        List<int[]> neighbors = new ArrayList<>();
        for (int[] dir : matrix) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx >= m || nx < 0 || ny >= n || ny < 0) {
                // 索引越界
                continue;
            }
            neighbors.add(new int[]{nx, ny});
        }
        return neighbors;
    }
    public int minimumEffortPath(int[][] heights) {
        int m=heights.length,n=heights[0].length;
        // 定义(0,0)到(i,j)的最小体力消耗是effortTo[i][j]
        int[][] effortTo=new int[m][n];
        // 初始化正无穷大
        for (int i=0;i<m;i++){
            Arrays.fill(effortTo[i],Integer.MAX_VALUE);
        }
        effortTo[0][0]=0;
        //优先级队列
        Queue<State> pq = new PriorityQueue<>((a, b) -> {
            return a.effortFromStart - b.effortFromStart;
        });
        // 从起点开始进行
        pq.offer(new State(0,0,0));
        while (!pq.isEmpty()){
            State curState = pq.poll();
            int curX=curState.x;
            int curY=curState.y;
            int curEffortFromStart = curState.effortFromStart;
            if (curX==m-1 && curY==n-1){
                return curEffortFromStart;
            }
            if (curEffortFromStart>effortTo[curX][curY]){
                continue;
            }
            //将(curX,curY)装进队列
            for (int[] neighbor : adj(heights, curX, curY)) {
                int nextX = neighbor[0];
                int nextY = neighbor[1];
                // 计算从 (curX, curY) 达到 (nextX, nextY) 的消耗
                int effortToNextNode = Math.max(
                        effortTo[curX][curY],
                        Math.abs(heights[curX][curY] - heights[nextX][nextY])
                );
                // 更新 dp table
                if (effortTo[nextX][nextY] > effortToNextNode) {
                    effortTo[nextX][nextY] = effortToNextNode;
                    pq.offer(new State(nextX, nextY, effortToNextNode));
                }
            }
        }
        return 1;
    }
}
